/*************************************************************************
> File Name: dynamicProgramming.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-13 14:24:10
> Description:
55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
************************************************************************/

// 思路：
// 数组f[i]记录位置i能否可达，0为不可达，1为可达
// 遍历数组，该位置可达则将该位置步数能到的所有地方记为可达
// 遍历时，每次最大跳跃之间，假若有可能依靠中间位置跳跃的更远，则在中间位置再次更新跳跃距离
// 若终点可达 则终点位1

#include <vector>
using namespace std;

class Solution
{
public:
    bool canJump(vector<int> &nums)
    {
        int length = nums.size(), jump = 0;
        vector<bool> f(length, false);
        // 所有不可达
        for (int i = 0; i < length; i++)
        {
            if (jump >= 0)
            {
                f[i] = 1;
            }
            else
            {
                return false;
            }
            if (jump < nums[i]) // 有中间点可以跳跃更远，更换中间点
            {
                jump = nums[i];
            }
            jump--;
        }
        return f[length - 1] == 1;
    }
};
